# -*- coding: utf-8 -*-

# 问题描述
# 给定一个字符串 (s) 和一个字符模式 (p)。实现支持 '.' 和 '*' 的正则表达式匹配
# '.' 匹配任意单个字符。
# '*' 匹配零个或多个前面的元素。
# 匹配应该覆盖整个字符串 (s) ，而不是部分字符串

# 说明:
# s 可能为空，且只包含从 a-z 的小写字母。
# p 可能为空，且只包含从 a-z 的小写字母，以及字符 . 和 *

# 示例 1:
# 输入:
# s = "aa"
# p = "a"
# 输出: false
# 解释: "a" 无法匹配 "aa" 整个字符串

# 示例 2:
# 输入:
# s = "aa"
# p = "a*"
# 输出: true
# 解释: '*' 代表可匹配零个或多个前面的元素, 即可以匹配 'a' 。因此, 重复 'a' 一次, 字符串可变为 "aa"

# 示例 3:
# 输入:
# s = "ab"
# p = ".*"
# 输出: true
# 解释: ".*" 表示可匹配零个或多个('*')任意字符('.')

# 示例 4:
# 输入:
# s = "aab"
# p = "c*a*b"
# 输出: true
# 解释: 'c' 可以不被重复, 'a' 可以被重复一次。因此可以匹配字符串 "aab"

# 示例 5:
# 输入:
# s = "mississippi"
# p = "mis*is*p*."
# 输出: false

# 前2个自己的解决方法错误的地方，解题过程中已经意识到解题思路的时间复杂度是m*n，可是却按照m+n的时间复杂度再写代码
# 所以一直都很别扭

# 直接对比，补丁打补丁打补丁的方式进行解答...一直当再也无法进行下去了，不开心
# 主要没有考虑到的地方:
# ".*ab"、"ab"、"cabab"
# 直接从前向后，不考虑后续内容时.*从什么时候开始匹配
# "ab*a*c*a"、"aba"、"abaa"、"abca"
# "a*c*"是匹配到a还是匹配到c
# 总结：
# 对于同一段正则它匹配的位置根据被匹配的字符串的不同能够表达出多种不同的语义
# 因而匹配时需要同时考虑匹配前后的字符串，通过一次遍历完成匹配的思路是不合理的，因而抛弃了以下的算法

# class Solution(object):
#     def isMatch(self, s, p):
#         """
#         :type s: str
#         :type p: str
#         :rtype: bool
#         """
#         while len(p)!=0 and p[0]=="*":
#             p = p[1 : len(p)];

#         if len(p)==0 and len(s)==0:
#             return True;

#         if len(p)==0 and len(s)!=0:
#             return False;

#         next_expect_index = 0;
#         next_match_index = 0;
#         asterisk_c = None;
#         asterisk_c_use_count = 0;
#         while (next_expect_index < len(p) or asterisk_c != None) and next_match_index < len(s):
#             next_expect_c = None;
#             if next_expect_index < len(p):
#                 next_expect_c = p[next_expect_index];

#             if next_expect_c == "*":
#                 asterisk_c = p[next_expect_index - 1];
#                 next_expect_index += 1;
#                 continue;

#             next_match_c = s[next_match_index];
#             if asterisk_c != None and asterisk_c != "." and next_match_c != asterisk_c:
#                 asterisk_c = None;
#                 asterisk_c_use_count = 0;

#             print [next_match_c, next_expect_c, asterisk_c];

#             if next_expect_c == next_match_c or (asterisk_c == None and next_expect_c == "."):
#                 next_expect_index += 1;
#                 next_match_index += 1;
#             elif asterisk_c != None:
#                 next_match_index += 1;
#                 asterisk_c_use_count += 1;
#             elif next_expect_index + 1 < len(p) and p[next_expect_index + 1] == "*":
#                 next_expect_index += 2;
#             else:
#                 return False;

#         if next_match_index != len(s):
#             return False;

#         while next_expect_index < len(p):
#             if p[next_expect_index] == "*":
#                 next_expect_index += 1;
#                 continue;
#             if next_expect_index + 1 < len(p) and p[next_expect_index + 1] == "*":
#                 next_expect_index += 2;
#                 continue;
#             if (p[next_expect_index] == asterisk_c) and asterisk_c_use_count > 0:
#                 next_expect_index += 1;
#                 asterisk_c_use_count -= 1;
#                 continue;
#             if asterisk_c == "." and asterisk_c_use_count > 0:
#                 next_expect_index += 1;
#                 asterisk_c_use_count -= 1;
#                 continue;
#             break;

#         if next_expect_index != len(p):
#             return False;

#         return True;


# 同时有多个符合匹配规则是要怎么选择
# "ababc" "a*b*abca*b*c*"
# "abab" "a*b*aba*b*"
# "ab" "a*b*aba*b*"
# 直接对比，对比失败后跳过一位a*重新对比

# ".*"怎么处理？".*"可能匹配到多个字符，不能直接跳过 !!!!! 那么上面a*的跳过也是有问题的，啊啊啊啊啊啊啊啊，要疯了，要疯了
# "aasdfasdfasdfasdfas" "aasdf.*asdf.*asdf.*asdf.*s"
# 再次放弃治疗，查答案去了...

# class Solution(object):
#     def isMatch(self, s, p):
#         """
#         :type s: str
#         :type p: str
#         :rtype: bool
#         """
#         # 把匹配字符串按照语义划分成块儿
#         split_p = [];
#         index = 0;
#         while index < len(p):
#             if p[index] != "*" and index + 1 < len(p) and p[index + 1] == "*":
#                 split_p.append(p[index : index + 2]);
#                 index += 2;
#             else:
#                 split_p.append(p[index]);
#                 index += 1;
#         # print split_p;

#         index_match = 0;
#         index_match_end = len(s);
#         index_split = 0;
#         index_split_end = len(split_p);
#         # 从后向前过滤掉确定匹配的内容
#         while True:
#             if index_split_end <= index_split or index_match_end <= index_match:
#                 break;
#             if len(split_p[index_split_end - 1]) == 1:
#                 if split_p[index_split_end - 1] == "." or split_p[index_split_end - 1] == s[index_match_end - 1]:
#                     index_match_end -= 1;
#                     index_split_end -= 1;
#                 else:
#                     return False;
#             elif len(split_p[index_split_end - 1]) == 2 and (split_p[index_split_end - 1][0] != "." and split_p[index_split_end - 1][0] != s[index_match_end - 1]):
#                 index_split_end -= 1;
#             else:
#                 break;

#         index_star_split = len(split_p);
#         index_star_match = 0;
#         while True:
#             print [index_match ,index_match_end , "", index_split, index_split_end, "", index_star_split, index_star_match];

#             if index_split == index_split_end and index_match == index_match_end:
#                 return True;

#             if index_match == index_match_end and index_split < index_split_end and len(split_p[index_split])==2:
#                 print "jump";
#                 index_split += 1;
#                 continue;

#             if index_match == index_match_end or index_split == index_split_end:
#                 if index_star_split + 1 < len(split_p) and len(split_p[index_star_split]) == 2:
#                     index_split = index_star_split + 1;
#                     index_star_split = len(split_p);
#                     index_match = index_star_match;
#                     print "back";
#                     continue;
#                 return False;

#             print [s[index_match], split_p[index_split]];

#             # 从前向后直接过滤掉确定匹配
#             if len(split_p[index_split]) == 1:
#                 if (split_p[index_split] == "." or split_p[index_split] == s[index_match]):
#                     index_match += 1;
#                     index_split += 1;
#                     continue;
#                 else:
#                     return False;
#             elif len(split_p[index_split]) == 2 and split_p[index_split][0] != "." and split_p[index_split][0] != s[index_match]:
#                 index_split += 1;
#                 continue;

#             if len(split_p[index_split]) == 2:
#                 if index_split < index_star_split:
#                     index_star_split = index_split;
#                     index_star_match = index_match;
#                 if(split_p[index_split][0] == "." or split_p[index_split][0] == s[index_match]):
#                     index_match += 1;
#                 else:
#                     index_split += 1;




# # 使用递归的思路解决问题
# class Solution(object):
#     def isMatch(self, s, p):
#         """
#         :type s: str
#         :type p: str
#         :rtype: bool
#         """
#         if len(p) == 0:
#             return len(s) == 0;

#         if len(p) == 1:
#             return len(s) == 1 and (p[0] == "." or p[0] == s[0]);

#         if p[1] != "*":
#             if len(s) == 0:
#                 return False;
#             if p[0] == "." or p[0] == s[0]:
#                 return self.isMatch(s[1: ], p[1: ]);
#             return False;

#         while len(s) > 0 and (p[0] == "." or p[0] == s[0]):
#             if self.isMatch(s, p[2: ]):
#                 return True;
#             s = s[1: ];
#         return self.isMatch(s, p[2: ]);




# 动态规划的思路解决问题，动态规划？
# This problem has a typical solution using Dynamic Programming. We define the state P[i][j] to be true if s[0..i) matches p[0..j) and false otherwise. Then the state equations are:

# P[i][j] = P[i - 1][j - 1], if p[j - 1] != '*' && (s[i - 1] == p[j - 1] || p[j - 1] == '.');
# P[i][j] = P[i][j - 2], if p[j - 1] == '*' and the pattern repeats for 0 times;
# P[i][j] = P[i - 1][j] && (s[i - 1] == p[j - 2] || p[j - 2] == '.'), if p[j - 1] == '*' and the pattern repeats for at least 1 times.
# Putting these together, we will have the following code.

# class Solution {
# public:
#     bool isMatch(string s, string p) {
#         int m = s.length(), n = p.length(); 
#         vector<vector<bool> > dp(m + 1, vector<bool> (n + 1, false));
#         dp[0][0] = true;
#         for (int i = 0; i <= m; i++)
#             for (int j = 1; j <= n; j++)
#                 if (p[j - 1] == '*')
#                     dp[i][j] = dp[i][j - 2] || (i > 0 && (s[i - 1] == p[j - 2] || p[j - 2] == '.') && dp[i - 1][j]);
#                 else dp[i][j] = i > 0 && dp[i - 1][j - 1] && (s[i - 1] == p[j - 1] || p[j - 1] == '.');
#         return dp[m][n];
#     }
# };

# 解题的思路是：
# 已知，所有.的位置[i,j]的匹配情况，推断?所在位置的匹配情况，最终推断出全盘的匹配状况
#         
#         
#    ?

# 文字描述
# 分三种情况
# 情况1：无"*"的情况，"pabc"和"pabd"进行匹配，已知[2,2]即"pa"和"pa"的匹配情况，求[3,3]即"pab"和"pab"的匹配情况
#  获得公式 dp[i+1][j+1] = dp[i][j] and p[j] in [s[i], "."]
#  公式说明 {"pab", "pab"} = {"pa", "pa"} and "b" in ["b", "."]
# 
# 情况2：有"*"并且"*"生效的情况 "paaaaa"和"pa*"进行匹配，已知[3, 3]即"paa"和"pa*"的匹配情况，求[4, 3]即"paaa"和"pa*"的匹配情况
#  获得公式 dp[i+1][j] = dp[i][j] and p[j - 1] in [s[i], "."]
#  公式说明 {"paaa", "pa*"} = {"paa", "pa*"} and "a" in ["a", "."]
#  
# 情况3：有"*"但是"*"不生效的情况 "paaaaa"和"pb*a*"进行匹配，已知[1, 1]即"p"和"p"的匹配情况，求[1, 3]即"p"和"pa*"的匹配情况
#  获得公式 dp[i][j+2] = dp[i][j] and p[j] not in [s[i], "."]
#  公式说明 {"p", "pb*"} = {"p", "p"} and "b" not in["p", "."]
#  
# 有以上公式可得知一下推理情况
#  dp[i][j]
#  => dp[i+1][j+1]
#  => dp[i+1][j]
#  => dp[i][j+2]
#  
#  公式1，当i=0时，即""和"" 或者 ""和"p" 或者 ""和"pa"进行匹配，因而可以很容易获得，是已知的条件
#  "abcdem"和"abcdem", 因无"*"存在因而只可能会进行等长匹配所以一定能够求得结果
#  #?????
#  #?????
#  #?????
#  #?????
#  #?????
#  #?????
#  因而纯粹有公式可以推断出一下情况
#  #?????
#  ##????
#  ###???
#  ####??
#  #####?
#  ######
#  因而在没有"*"的情况下，必然能够找到最终的答案
#  
#  而在有"*"的情况下，我们又通过公式2,3确定了"*"生效和"*"不生效2种情况都考虑到求解的范围内
#  所以这3个条件是能够充分求得我们想要的结果的


class Solution(object):
    def isMatch(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: bool
        """
        length_s = len(s);
        length_p = len(p);
        dp = [[False] * (length_p + 1) for x in xrange(0,length_s + 1)];
        dp[0][0] = True;
        # print dp;
        # print "\n";
        
        # 为什么index_s从0开始，而index_p从1开始
        # 因为存在[0,2] == Ture这种情况，
        # 例如：""和"a*"
        # 而除了[0, 0] == True这种情况，并不存在[?, 0] == True的可能性
        for index_s in xrange(0, length_s + 1):
            for index_p in xrange(1, length_p + 1):
                if p[index_p - 1] != "*":
                    dp[index_s][index_p] = index_s > 0 and dp[index_s - 1][index_p - 1] and (p[index_p - 1] == "." or p[index_p - 1] == s[index_s - 1]);
                else:
                    dp[index_s][index_p] = dp[index_s][index_p - 2] or (index_s > 0 and (p[index_p - 2] == "." or p[index_p - 2] == s[index_s - 1])) and dp[index_s - 1][index_p];
                print dp;
            print "\n";
        return dp[length_s][length_p];



t = Solution();

t_list = [];
# t_list.append(["aa", "a", False]);
# t_list.append(["aa", "a*", True]);
# t_list.append(["ab", ".*", True]);
# t_list.append(["aab", "c*a*b", True]);
# t_list.append(["aaa", "a*a", True]);
# t_list.append(["aaaaaaaa", "a*a", True]);
# t_list.append(["mississippi", "mis*is*p*.", False]);
# t_list.append(["mississippi", "mis*is*ip*.", True]);
# t_list.append(["aaaca", "ab*a*c*a", True]);
# t_list.append(["aaa", "ab*a*c*aa", True]);
# t_list.append(["aaa", "ab*a*c*a", True]);
# t_list.append(["bbbba", ".*a*a", True]);
# t_list.append(["ab", ".*c", False]);
# t_list.append(["ab", "a*b*", True]);
# t_list.append(["ab", "a*b*ab", True]);
# t_list.append(["ab", "a*b*aba*b*", True]);
# t_list.append(["ababc", "a*b*abc", True]);
# t_list.append(["ababc", "a*b*aba*b*c", True]);
# t_list.append(["ababc", "a*b*abca*b*c*", True]);
# t_list.append(["bbab", "b*a*", False]);
# t_list.append(["aasdfasdfasdfasdfas", "aasdf.*asdf.*asdf.*asdf.*s", True]);
# t_list.append(["aasdfasdfasdfas", ".*asdf.*asdf.*asdf.*s", True]);
t_list.append(["paaa", ".*", True]);

for t_v in t_list:
    if t.isMatch(t_v[0], t_v[1]) != t_v[2]:
        print u"失败:";
        print t_v;
        break;
    else:
        print ".\n";